/* lis: longest increasing subsequence */
#include <stdio.h>
#include <stdlib.h>

void printLis(int *a, int *b, int current)
{
  if (b[current] >= 0)
    printLis(a, b, b[current]);
  printf("%d ", a[current]);
}

void lis(int *a, int len)
{
  int i, j;
  int *f = (int *)malloc(len * sizeof(int)); /* f[i]: length of lis which ends with a[i] */
  int *b = (int *)malloc(len * sizeof(int)); /* a[b[i]] -> a[i] */

  f[0] = 1;
  b[0] = -1;
  for (i = 1; i < len; i++) {
    f[i] = 1;
    b[i] = -1;
    for (j = 0; j < i; j++) {
      if (a[j] < a[i] && f[j] > f[i] - 1) { 
	f[i] = f[j] + 1;
	b[i] = j;
      }
    }
  }
  /* find the last element of lis */
  j = f[0];
  for (i = 0; i < len; i++)
    if (f[i] > j)
      j = i;
  printLis(a, b, j);
  printf("\n");
  free(f);
  free(b);
}

int main()
{
  int i, j;
  int n[] = {1000, 3000, 200000};
  int *a;

  srand(time(0));
  for (i = 0; i < 3; i++) {
    a = (int *)malloc(n[i] * sizeof(int));
    for (j = 0; j < n[i]; j++)
      a[j] = (int)(n[i] * 1.0 / RAND_MAX * rand()); 
    printf("The longest increasing subsequence of %d random integers is:\n", n[i]);
    lis(a, n[i]);
    free(a);
  }

  return 0;
}
